import java.util.*;

class Solution1 {
    public int lenLongestFibSubseq(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }
        int[][] dp = new int[n][n];
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++) {
                dp[i][j] = 2;
            }
        }
        //k j i
        int ret = 0;
        for(int i = 1; i<n; i++) {
            for(int j = 0;j<i; j++) {
                if(map.containsKey(arr[i] - arr[j])) {
                    int k = map.get(arr[i] - arr[j]);
                    if(k < j) {
                        dp[j][i] = Math.max(dp[k][j] + 1, dp[j][i]);
                    }
                }
                ret = Math.max(ret, dp[j][i]);
            }
        }

        if(ret <= 2) return 0;
        return ret;
    }
}


//暴力解法
class Solution2 {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for(int i = 0; i<n; i++) {
            for(int j = 0;j<n;j++) {
                dp[i][j] = 2;
            }
        }
        dp[0][0] = 1;
        int ret = 0;
        for(int i = 1; i<n; i++ ) {
            for(int j = 0; j < i; j++) {
                for(int k = j-1; k>=0 ;k--) {
                    if(nums[k] == 2*nums[j] - nums[i]) {
                        dp[j][i] = Math.max(dp[k][j] + 1, dp[j][i]);
                        break;
                    }
                }
                ret = Math.max(ret,dp[j][i]);
            }
        }
        return ret;
    }
}

//优化
class Solution3 {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for(int i = 0; i<n; i++) {
            for(int j = 0;j<n;j++) {
                dp[i][j] = 2;
            }
        }
        dp[0][0] = 1;
        int ret = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i<n; i++ ) {
            for(int j = i+1; j < n; j++) {
                if(map.containsKey(2*nums[i] - nums[j])) {
                    int k = map.get(2*nums[i] - nums[j]);
                    dp[i][j] = Math.max(dp[k][i] + 1, dp[i][j]);
                }
                ret = Math.max(ret,dp[i][j]);
            }
            map.put(nums[i], i);
        }
        return ret;
    }
}


class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

class Solution4 {
    public ListNode sortList(ListNode head) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        ListNode cur = head;
        while(cur!=null) {
            queue.add(cur);
            cur = cur.next;
        }
        ListNode newHead = new ListNode();
        cur = newHead;
        while(!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
        }
        cur.next = null;
        return newHead.next;
    }
}

class Solution5 {
    public ListNode oddEvenList(ListNode head) {
        ListNode curA = head, curB = head.next;
        if(curB == null) return curA;
        ListNode newHeadA = new ListNode();
        ListNode newHeadB = new ListNode();
        newHeadA.next = curA;
        newHeadB.next = curB;

        while(curA!=null && curB!=null) {
            curA.next = curB.next;
            if(curB.next == null) {
                curB.next = null;
            }else {
                curB.next = curB.next.next;
            }
            if(curA.next!=null) {
                curA = curA.next;
            }
            curB = curB.next;
        }
        curA.next = newHeadB.next;
        return newHeadA.next;
    }
}

class Solution6 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1, cur2 = list2;
        ListNode head = new ListNode();
        ListNode cur = head;
        while(cur1!=null && cur2!=null) {
            if(cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            }else {
                cur.next = cur2.next;
                cur2 = cur2.next;
            }
        }
        if(cur1!=null) {
            cur.next = cur1;
        }
        if(cur2!=null) {
            cur.next = cur2;
        }
        return head.next;
    }
}

// 删除链表中的重复节点
class Solution7 {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode newHead = new ListNode(0);
        ListNode tail = newHead;
        ListNode cur = pHead;
        while(cur!=null) {
            ListNode tmp = cur.next;
            int flag = 0;
            while(tmp != null && cur.val == tmp.val) {
                cur = cur.next;
                tmp = tmp.next;
                flag = 1;
            }
            if(flag == 0) {
                tail.next = cur;
                tail = tail.next;
            }
            cur = cur.next;
        }
        tail.next = null;
        return newHead.next;
    }
}

public class Test {
    public static void main(String[] args) {
        int[] nums = {3,6,9,12};
        int ret = new Solution2().longestArithSeqLength(nums);
        System.out.println(ret);
    }
}
